package fun.ticsmyc.question.dp;

/**
 *
 *   dp[i] = dp[i-2]+2   ， 当str[i] ==')' && str[i-1] =='('时
 *   dp[i] = dp[i-1]+dp[i-dp[i-1]-2] +2  ， 当str[i]==')'且str[i-1] ==')' 且str[i-dp[i-1]]=='('时
 * @author Ticsmyc
 * @date 2021-03-08 15:36
 */
public class 最长有效括号 {

    public int longestValidParentheses(String s) {
        if(s==null || s.length()<1){
            return 0;
        }
        int ans=0;

        char[] str = s.toCharArray();
        int[] dp = new int[str.length];
        dp[0]=0;
        for(int i=1;i<str.length;++i){
            if(str[i]==')'){
                if(str[i-1]=='('){
                    dp[i] = 2 + (i-2>=0?dp[i-2]:0);
                }else{
                    //两个)
                    if(dp[i-1]!=0 && i-1-dp[i-1] >=0 && str[i-1-dp[i-1]]=='('){
                        dp[i] = dp[i-1] +2 +(i-dp[i-1]-2 >=0 ? dp[i-dp[i-1]-2]:0);
                    }
                }
                ans=Math.max(dp[i],ans);
            }
        }
        return ans;
    }
}
